package com.other;

import java.util.Arrays;

/**
 * @author yyh
 * @date 2024年11月12日 上午10:11
 * <a href="https://leetcode.cn/problems/koko-eating-bananas/">...</a>
 */
public class MinEatingSpeed {

    //珂珂喜欢吃香蕉。这里有 n 堆香蕉，第 i 堆中有 piles[i] 根香蕉。警卫已经离开了，将在 h 小时后回来。
    //珂珂可以决定她吃香蕉的速度 k （单位：根/小时）。每个小时，她将会选择一堆香蕉，从中吃掉 k 根。如果这堆香蕉少于 k 根，她将吃掉这堆的所有香蕉，然后这一小时内不会再吃更多的香蕉。
    //珂珂喜欢慢慢吃，但仍然想在警卫回来前吃掉所有的香蕉。
    //
    //返回她可以在 h 小时内吃掉所有香蕉的最小速度 k（k 为整数）。
    //
    //示例 1：
    //输入：piles = [3,6,7,11], h = 8
    //输出：4

    //示例 2：
    //输入：piles = [30,11,23,4,20], h = 5
    //输出：30

    //示例 3：
    //输入：piles = [30,11,23,4,20], h = 6
    //输出：23

    public int minEatingSpeed(int[] piles, int h) {
        int n = piles.length;
        if (n == 0 || n > h) {
            return 0;
        }

        Arrays.sort(piles);
        if (n == h) {
            return piles[n - 1];
        }

        int min = Integer.MAX_VALUE;
        int left = 0;
        int right = piles[n - 1];
        int mid = (left + right) / 2;
        while (left <= right) {
            if (mid == 0) {
                break;
            }
            int cost = cost(piles, mid);
            if (cost <= h) {
                min = Math.min(min, mid);
                right = mid - 1;
            } else {
                left = mid + 1;
            }
            mid = (left + right) / 2;
        }
        return min;
    }

    private int cost(int[] piles,int x ) {
        int cost = piles.length;
        for (int i = piles.length - 1; i >= 0; i--) {
            if (piles[i] <= x) {
                break;
            }
            cost += piles[i] / x - 1;
            cost += piles[i] % x == 0 ? 0 : 1;
        }
        return cost;
    }

    public static void main(String[] args) {
        MinEatingSpeed main = new MinEatingSpeed();
//        System.out.println(main.minEatingSpeed(new int[]{3, 6, 7, 11}, 8));
//        System.out.println(main.minEatingSpeed(new int[]{10, 11}, 4));
        System.out.println(main.minEatingSpeed(new int[]{805306368,805306368,805306368}, 1000000000));
    }
}
